#include <stdio.h>
#include <time.h>

int maxseqsum(int arr[], int n) {
    int max_sum = 0, curr_sum = 0;
    for (int i = 0; i < n; i++) {
        curr_sum += arr[i];
        if (curr_sum > max_sum) {
            max_sum = curr_sum;
        } else if (curr_sum < 0) {
            curr_sum = 0;
        }
    }
    return max_sum;
}

int  main(int argc, char *argv[]) {

    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);


    clock_t start, end;
    double cpu_time_used;


    start = clock();
    int max_sum = maxseqsum(arr, n);
    end = clock();

    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("Maximum subarray sum is %d\n", max_sum);
    printf("Time taken: %f seconds\n", cpu_time_used);

    return 0;
}